// 6.1　二叉堆
function maxHeapDown(array, i, n) {
    var parent = i;
    while (parent < n) {
      var left = 2 * parent + 1;
      var bigChild = null;
      if( left < n ){ // 存在左孩子结点(判定是否越界)
        bigChild = left;
        var right = left + 1;
        if(right < n && array[left] < array[right]){
           // 存在右孩子结点，并且比左孩子结点大
           bigChild = right;
        }
      }
      if(bigChild !== null && array[bigChild] > array[parent]){
        // 让父结点与大孩子结点互换，确保值大的在上面
        swap(array, bigChild, parent);
        parent = bigChild; // 修正父结点的索引
      }else{
         break;
      }
    } 
}  

function swap(array, a, b) {
  var temp = array[a];
  array[a] = array[b];
  array[b] = temp;
}

// function heapSort(array) {
//   var n = array.length;
//   // 数组现在分成两个区域，左边是大顶堆，右边是有序区
//   for (var i = n >> 1; i >= 0; i--) {
//     maxHeapDown(array, i, n);// 找到最后一个非叶子结点并将其与它的孩子结点交换
//   }
//   // 现在array[0]是大项堆的堆顶，是最大的
//   for (var i = n - 1; i > 0; i--) {
//     swap(array, 0, i); // 将堆顶挪到有序区的最前面
//     maxHeapDown(array, 0, i); // 重新有序化变小了的大顶堆
//   }
// }
// var array = [3, 6, 8, 1, 9, 0, 4, 5, 2];
// heapSort(array);
// console.log(array);
// [0,1,2,3,4,5,6,8,9]

// 6.2　堆排序
function minHeapDown(array, i, n) {
    var parent = i;
    while (parent < n) {
      var left = 2 * parent + 1;
      var tinyChild = null;
      if(left < n ){
        tinyChild = left;
        var right = left+1;
        if(right < n && array[left] > array[right]){
           // 存在右孩子结点，并且比左孩子结点小
           tinyChild = right;
        }
      }
      if(tinyChild !== null && array[tinyChild] < array[parent]){
        // 让父结点与小孩子结点互换，确保值小的在上面
        swap(array, tinyChild, parent);
        parent = tinyChild; // 修正父结点的索引
      }else{
        break;
      }
    }
  }
  
  
//   function heapSort(array) {
//     var n = array.length;
//     // 数组现在分成两个区域，左边是小顶堆，右边是有序区
//     for (var i = n >> 1; i >= 0; i--) {
//       minHeapDown(array, i, n);
//     }
//     for (var i = n - 1; i > 0; i--) {
//       swap(array, 0, i); // 将堆顶挪到有序区的最前面
//       minHeapDown(array, 0, i); // 需要重新有序化成小顶堆
//     }
//   }
//   var array = [3, 6, 8, 1, 9, 0, 4, 5, 2];
//   heapSort(array);
//   console.log(array);
  // [9, 8, 6, 5, 4, 3, 2, 1, 0]



//   6.3　TopK问题

function findKthLargest(array, k) {// k从0开始
  var n = array.length;
  for (var i = (n >> 1); i >= 0; i--) {
    maxHeapDown(array, i, n);
  }
  if (k === 0) {
    return array[0]; // 最大数
  }
  k--;
  for (var i = n - 1; i > 0; i--) {
    swap(array, 0, i);
    maxHeapDown(array, 0, i);
    if (k-- === 0) {
      return array[0];
    }
  }
  throw `${k}超过数组长度!`;
}
// 求最大数
var el = findKthLargest([3, 11, 1, 5, 6, 9, 7, 8], 0);
console.log(el);
// 求第二大数
var el = findKthLargest([3, 11, 1, 5, 6, 9, 7, 8], 1);
console.log(el);
// 求第三大数
var el = findKthLargest([3, 11, 1, 5, 6, 9, 7, 8], 2);
console.log(el);

function findLargest(array, k) {
    var ret = [],
    n = array.length;
    // 将数据分成两部分：体制内的与体制外的
    for (var i = 0; i < k; i++) {
      ret[i] = array[i];
    }
    // 将体制内的元素转换成小顶堆，方便优胜劣汰
    for (var j = k >> 1; j >= 0; --j) {
      minHeapDown(ret, j, k);
    }
    for (var j = k; j < n; j++) {
      if (ret[0] < array[j]) { // 用外部的元素顶替小顶堆的堆顶
        ret[0] = array[j];
        minHeapDown(ret, 0, k); // 继续转换小顶堆，将最小的值置顶
      }
    }
    return ret;
  }
  var ret = findLargest([3, 11, 1, 5, 6, 9, 7, 8], 4);
  console.log(ret);
  // [7, 9, 8, 11]

//   6.4　优先队列
class PriorityQueue {
    constructor(){
      this.heap = [];
    }
    // 大顶堆的优先队列
    // push(el){
    //     var array = this.heap;
    //     array.push(el);
    //     var child = array.length - 1;// 知道“孩子”找“父亲”
    //     while (true) {
    //       var parent = (child - 1) >> 1;
    //       if (array[parent] < array[child]) {
    //         swap(array, child, parent);// 让大的在上面
    //         child = parent;
    //       } else {
    //         break;
    //       }
    //     }
    // } 
    // pop(el) {
    //     var array = this.heap, index = 0;
    //     for (var i = 0; i < array.length; i++) {
    //       if (array[i] === el) {
    //         index = i;
    //         break;
    //       }
    //     }
    //     var target = array[index];
    //     swap(array, index, array.length - 1);
    //     // 知道“父亲”，找“孩子”，不断往下找（数组的右边方向）
    //     var parent = 0, child = parent * 2 + 1;
    //     while (true) {
    //       if (array[child] < array[child + 1] && array[child + 1] != target) {// 找到大的“孩子”
    //         child++;
    //       }
    //       // 让大的“孩子”与“父亲”交换
    //       if (array[parent] < array[child] && array[child] != target) {
    //         swap(array, parent, child);
    //         parent = child;
    //         child = parent * 2 + 1; // 不断往右走
    //       } else {
    //         break;
    //       }
    //     }
    //     return array.pop();
    // }
    // 小顶堆的优先队列
    push(el){
        var array = this.heap;
        array.push(el);
        var child = array.length - 1;// 知道“孩子”找“父亲”
        while (true) {
          var parent = (child - 1) >> 1;
          if (array[parent] > array[child]) { 
            swap(array, child, parent);// 让小的在上面
            child = parent;
          } else {
            break;
          }
        }
    } 
    pop(el) {
        var array = this.heap, index = 0;
        for (var i = 0; i < array.length; i++) {
          if (array[i] === el) {
            index = i;
            break;
          }
        }
        var target = array[index];
        swap(array, index, array.length - 1);
        // 知道“父亲”找“孩子”，不断往下找（数组的右边方向）
        var parent = 0, child = parent * 2 + 1;
        while (true) {
          if (array[child] > array[child + 1] && array[child + 1] != target) {// 找到小的“孩子”
            child++;
          }
          // 让小的“孩子”与“父亲”交换
          if (array[parent] > array[child] && array[child] != target) {
            swap(array, parent, child);
            parent = child;
            child = parent * 2 + 1; // 不断往右走
          } else {
            break;
          }
        }
        return array.pop();
    }
    max(){// 返回最大的元素
      return this.heap[0];
    }  
    size(){// 大小
      return this.heap.length;
    } 
    empty(){// 是否为空
      return !this.heap.length;
    }
  }
var a = new PriorityQueue();
a.push(1);
a.push(13);
a.push(4);
a.push(17);
a.push(2);
console.log(a.heap+"");
a.push(18);
console.log(a.heap+"");
a.push(15);
console.log(a.heap+"");
a.push(29);
console.log(a.heap+"");
a.pop();
console.log(a.heap+"");


// 6.5　丑数
var nthUglyNumber = function (n) {
    var hash = {};
    var queue = new PriorityQueue();
    queue.push(1);
    hash[1] = true;
    var factors = [2, 3, 5], num;
    for (var i = 0; i <= n; i++) {
      num = queue.pop();
      for (var j = 0; j < 3; j++) {
        var next = num * factors[j];
        if (!hash[next]) {
          hash[next] = true;
          queue.push(next);
        }
      }
    }
    return num;
  };
  console.log(nthUglyNumber(1));
  console.log(nthUglyNumber(2));
  console.log(nthUglyNumber(3));
  console.log(nthUglyNumber(4));
  console.log(nthUglyNumber(5));
  console.log(nthUglyNumber(10));
  console.log(nthUglyNumber(400));
  console.log(nthUglyNumber(1212));